package com.hy;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:多数元素II
 * 给定一个大小为 n 的整数数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。
 * 总结：n个数，找出其中所有出现超过 ⌊ n/m ⌋ 次的元素。那么结果集就是m-1个结果
 *
 * case1: 直接使用map计数统计
 * case2: 使用摩尔投票法
 * User:Mr.Du
 * Date:2023/8/7
 * Time:16:08
 */
public class MajorityElement {

    public static List<Integer> majorityElement1(int[] nums, int k) {
        List<Integer> res = new ArrayList<>();
        Map<Integer, Integer> mp = new HashMap<>();
        for(int x : nums){
            mp.put(x, mp.getOrDefault(x, 0) +  1);
        }
        int len = nums.length / k;
        for(Integer i : mp.keySet()){
            if(mp.get(i) > len) res.add(i);
        }
        return res;
    }

    public static List<Integer> majorityElement(int[] nums) {
        List<Integer> res = new ArrayList<>();
        int res1 = nums[0], res2 = nums[0];
        int cnt1 = 0, cnt2 = 0;
        for(int x : nums){
            if(res1 == x){
                cnt1++;
                continue;
            }
            if(res2 == x){
                cnt2++;
                continue;
            }
            if(cnt1 == 0){
                res1 = x;
                cnt1++;
                continue;
            }
            if(cnt2 == 0){
                res2 = x;
                cnt2++;
                continue;
            }
            cnt1--;
            cnt2--;
        }
        cnt1 = 0;
        cnt2 = 0;
        for(int x : nums){
            if(res1 == x) cnt1++;
            else if(res2 == x) cnt2++;
        }
        if(cnt1 > nums.length / 3) res.add(res1);
        if(cnt2 > nums.length / 3) res.add(res2);
        return res;

    }

    public static void main(String[] args) {
        int[] nums = {1,1,2,2,7,7,8,8,9,3,9,3,9,3,9,3,9,3,9,3,9,3,9,3,9,3,9,3,9,3,9,3,9,3,9,3,9,3};
        List<Integer> res = majorityElement(nums);
        System.out.println(res);
    }


}
